1 Building Abstractions with Functions

We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.

A computational process is indeed much like a sorcerer’s idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory. The programs we use to conjure processes are like a sorcerer’s spells. They are carefully composed from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our processes to perform.

A computational process, in a correctly working computer, executes programs precisely and accurately. Thus, like the sorcerer’s apprentice, novice programmers must learn to understand and to anticipate the consequences of their conjuring. Even small errors (usually called bugs or glitches) in programs can have complex and unanticipated consequences.

Fortunately, learning to program is considerably less dangerous than learning sorcery, because the spirits we deal with are conveniently contained in a secure way. Real-world programming, however, requires care, expertise, and wisdom. A small bug in a computer-aided design program, for example, can lead to the catastrophic collapse of an airplane or a dam or the self-destruction of an industrial robot.

Master software engineers have the ability to organize programs so that they can be reasonably sure that the resulting processes will perform the tasks intended. They can visualize the behavior of their systems in advance. They know how to structure programs so that unanticipated problems do not lead to catastrophic consequences, and when problems do arise, they can debug their programs. Well-designed computational systems, like well-designed automobiles or nuclear reactors, are designed in a modular manner, so that the parts can be constructed, replaced, and debugged separately.

1.1 The Elements of Programming

A powerful programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes. Thus, when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for accomplishing this:

• primitive expressions, which represent the simplest entities the language is concerned with,

• means of combination, by which compound elements are built from simpler ones, and

• means of abstraction, by which compound elements can be named and manipulated as units.

In programming, we deal with two kinds of elements: functions and data. (Later we will discover that they are really not so distinct.) Informally, data is “stuff” that we want to manipulate, and functions are descriptions of the rules for manipulating the data. Thus, any powerful programming language should be able to describe primitive data and primitive functions and should have methods for combining and abstracting functions and data.

In this chapter we will deal only with simple numerical data so that we can focus on the rules for building functions.1 In later chapters we will see that these same rules allow us to build functions to manipulate compound data as well.

1.1.1 Expressions

One easy way to get started at programming in JavaScript is to interact with the JavaScript interpreter that is built into the browser you are using to view this page. We have set up the statements shown with a dark background such that you can click on them. The mouse click on JavaScript statements is programmed in such a way that a JavaScript interpreter is displayed, which can evaluate the statement and display the resulting value. By the way, the program that makes the mouse click on a JavaScript statement display the interpreter is itself written in JavaScript; we call it the script for the mouse click.

One kind of statement is an A simple kind of an expression is a number. (More precisely, the expression consists of the numerals that represent the number in base 10.) If you ask our script to display the interpreter for the expression statement

 486;

by clicking it, it will respond by creating a separate browser tab where the statement is shown, with the option to evaluate the statement. Click on the primitive expression statement, and see what happens!

Expressions representing numbers may be combined with operators (such as + or *) to form a compound expression that represents the application of a corresponding primitive function to those numbers. For example, evaluate any of the following expression statements1 by clicking on it:

 137 + 349;

 1000 - 334;

 5 * 99;

 10 / 5;

 2.7 + 10;

Expressions such as these, which contain other expressions as components, are called combinations. Combinations that are formed by an operator symbol in the middle, and operand expressions to the left and right of it, are called The value of an operator combination is obtained by applying the function specified by the operator to the arguments that are the values of the operands.

The convention of placing the operator between the operands is known as It follows the mathematical notation that the reader is most likely familiar with from school and everyday life. As in mathematics, operator combinations can be nested, that is, they can take arguments that themselves are operator combinations:

 (3 * 5) + (10 - 6);

As usual, parentheses are used to group operator combinations in order to avoid ambiguities. JavaScript also follows the usual conventions when parentheses are omitted; multiplication and division bind stronger than addition and subtraction. For example,

 3 * 5 + 10 / 2;

stands for

 (3 * 5) + (10 / 2);

We say that * and / have higher precedence than + and -. Sequences of additions and subtractions are read from left to right, as are sequences of multiplications and divisions. Thus,

 3 / 5 * 2 - 4 + 3;

stands for

 (((3 / 5) * 2) - 4) + 3;

We say that the operators +, -, * and / are left-associative.

It is we humans who might get confused by still relatively simple expressions such as

 3 * 2 * (4 + (3 - 5)) + 10 * (27 / 6);

which the interpreter would readily evaluate to be 57. We can help ourselves by writing such an expression in the form

 3 * 2 * (4 + (3 - 5)) 
 + 
 10 * (27 / 6);

to visually separate the major components of the expression.

The interpreter always operates in the same basic cycle: It reads a statement from the browser, evaluates the statement, and prints the result. This mode of operation is often expressed by saying that the interpreter runs in a read-eval-print loop. Observe in particular that it is not necessary to explicitly instruct the interpreter to print the value of the statement.

1.1.2 Naming and the Environment

A critical aspect of a programming language is the means it provides for using names to refer to computational objects, and our first such means are constants. We say that the name identifies a constant whose value is the object.

In JavaScript, we name constants using constant declarations. Typing

 const size = 2;

causes the interpreter to associate the value 2 with the name size. The purpose of the constant declaration is to create this association, and not to compute a particular value as for expression statements. The JavaScript specification demands that the special value undefined shall be the result of evaluating such constant declarations.

Once the name size has been associated with the number 2, we can refer to the value 2 by name as in

 size;

or

 5 * size;

Here are further examples of the use of const:

 const pi = 3.14159;

 const radius = 10;

 pi * radius * radius;

 const circumference = 2 * pi * radius;

 circumference;

Constant declaration is our language’s simplest means of abstraction, for it allow us to use simple names to refer to the results of compound operations, such as the circumference computed above. In general, computational objects may have very complex structures, and it would be extremely inconvenient to have to remember and repeat their details each time we want to use them. Indeed, complex programs are constructed by building, step by step, computational objects of increasing complexity.

It should be clear that the possibility of associating values with names and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).1

1.1.3 Evaluating Operator Combinations

One of our goals in this chapter is to isolate issues about process descriptions. As a case in point, let us consider that, in evaluating operator combinations, the interpreter proceeds as follows.

• To evaluate an operator combination, do the following:

  1. Evaluate the operand expressions of the combination.

  2. Apply the function that is denoted by the operator to the arguments that are the values of the operands.

Even this simple rule illustrates some important points about processes in general. First, observe that the first step dictates that in order to accomplish the evaluation process for an operator expression we must first perform the evaluation process on each operand of the operator combination. Thus, the evaluation rule is recursive in nature; that is, it includes, as one of its steps, the need to invoke the rule itself.

Notice how succinctly the idea of recursion can be used to express what, in the case of a deeply nested combination, would otherwise be viewed as a rather complicated process. For example, evaluating

 (2 + 4 * 6) * (3 + 12);

requires that the evaluation rule be applied to four different combinations. We can obtain a picture of this process by representing the combination in the form of a tree, as shown in Figure 1.1. Each combination is represented by a node with branches corresponding to the operator and the operands of the operator combination stemming from it. The terminal nodes (that is, nodes with no branches stemming from them) represent either operators or numbers. Viewing evaluation in terms of the tree, we can imagine that the values of the operands percolate upward, starting from the terminal nodes and then combining at higher and higher levels. In general, we shall see that recursion is a very powerful technique for dealing with hierarchical, treelike objects. In fact, the “percolate values upward” form of the evaluation rule is an example of a general kind of process known as tree accumulation.

 

Next, observe that the repeated application of the first step brings us to the point where we need to evaluate, not operator combinations, but primitive expressions such as numerals or names. We take care of the primitive cases by stipulating that

Notice the role of the environment in determining the meaning of the names in expressions. In JavaScript, it is meaningless to speak of the value of an expression such as x + 1 without specifying any information about the environment that would provide a meaning for the name x. As we shall see in chapter 3, the general notion of the environment as providing a context in which evaluation takes place will play an important role in our understanding of program execution.

Notice that the evaluation rule given above does not handle constant declarations. For instance, evaluating const x = 3; does not apply the = operator to two arguments, one of which is the value of the name x and the other of which is 3, since the purpose of the constant declaration is precisely to associate x with a value. (That is, the part x = 3 in the constant declaration const x = 3; is not an operator combination.)

The string “const” in the constant declaration is rendered in bold letters to indicate that it is a keyword in JavaScript. Keywords are reserved words that carry a particular meaning, and thus cannot be used as names. A keyword or a combination of keywords instructs the JavaScript interpreter to treat the respective statement in a special way. Each such syntactic form has its own evaluation rule. The various kinds of statements (each with its associated evaluation rule) constitute the syntax of the programming language.

1.1.4 Functions

We have identified in JavaScript some of the elements that must appear in any powerful programming language:

• Numbers and arithmetic operations are primitive data and functions.

• Nesting of combinations provides a means of combining operations.

• Constant declarations that associate names with values provide a limited means of abstraction.

Now we will learn about function declarations, a much more powerful abstraction technique by which a compound operation can be given a name and then referred to as a unit.

We begin by examining how to express the idea of “squaring.” We might say, “To square something, take it times itself.” This is expressed in our language as

 function square(x) {
     return x * x;
 }

We can understand this in the following way:

 function square(    x   ) { return x    *     x; }
 //  ^       ^       ^         ^    ^    ^     ^
 // To    square something,  take   it times itself.

We have here a compound function, which has been given the name square. The function represents the operation of multiplying something by itself. The thing to be multiplied is given a local name, x, which plays the same role that a pronoun plays in natural language. Evaluating the declaration creates this compound function and associates it with the name square.1

Our simplest form of a function declaration is

 function name( parameters ) { return expression; }

The $\textit{name}$ is a symbol to be associated with the function in the environment.2 The $\textit{parameters}$ are the names used within the body of the function to refer to the corresponding arguments of the function. The $\textit{expression}$ after the keyword return is the return expression that will yield the value of the function application when the parameters are replaced by the arguments to which the function is applied.3 The $\textit{parameters}$ are grouped within parentheses and separated by commas, just as they would be in an actual call to the function being declared.

Having declared the square function, we can now use it in a function application expression, which we turn into a statement using a semicolon:

 square(21);

The name square is the function expression of the application, and 21 is the argument expression.

 square(2 + 5);

Here, the argument expression is itself a compound expression, the operator expression 2 + 5.

 square(square(3));

Of course application expressions can also serve as argument expressions.

We can also use square as a building block in declaring other functions. For example, $x^2 +y^2$ can be expressed as

 square(x) + square(y);

We can easily declare a function sum_of_squares that, given any two numbers as arguments, produces the sum of their squares:

 function sum_of_squares(x,y) {
     return square(x) + square(y);
 }

Now we can use sum_of_squares as a building block in constructing further functions:

 function f(a) {
     return sum_of_squares(a + 1, a * 2);
 }

The application of functions such as sum_of_squares(3,4) is—after operator combination—the second kind of combination of expressions into larger expressions that we encounter. In addition to compound functions, JavaScript provides a number of primitive functions that are built into the interpreter. An example is the function math_log that computes the natural logarithm of its argument.4 Evaluating the application expression math_log(1) results in the number 0. Primitive functions are used in exactly the same way as compound functions. Indeed, one could not tell by looking at the definition of sum_of_squares given above whether square was built into the interpreter, like math_log, or defined as a compound function.

1.1.5 The Substitution Model for Function Application

To evaluate an application combination, the interpreter follows a similar process as for operator combinations, which we described in section 1.1.3. That is, the interpreter evaluates the elements of the combination and applies the function (which is the value of the function expression) to the arguments (which are the values of the argument expressions of the application combination).

In more detail, the interpreter proceeds as follows when evaluating application combinations:

• To evaluate an application combination of the form

   function-expression ( argument-expressions )

  do the following:

  1. Evaluate the function expression of the application combination, resulting in the function to be applied.

  2. Evaluate the argument expressions of the combination.

  3. Apply the function to the arguments:

     • If the function is primitive, we simply apply the corresponding mathematical function to the arguments.

     • If the function is compound, we evaluate the return expression of the function with each parameter replaced by the corresponding argument.

To illustrate this process, let’s evaluate the application combination

 f(5);

Evaluating the name f results in the function declared in section 1.1.4. Evaluating the argument expression 5 yields the argument value 5. Now, we retrieve the return expression of f:

 sum_of_squares(a + 1, a * 2)

in which we replace the parameter a by the argument 5:

 sum_of_squares(5 + 1, 5 * 2)

Thus the problem reduces to the evaluation of an application combination with two arguments and a function expression sum_of_squares. Evaluating this combination involves three subproblems. We must evaluate the function expression to get the function to be applied, and we must evaluate the argument expressions to get the arguments. Now 5 + 1 produces 6 and 5 * 2 produces 10, so we must apply the sum_of_squares function to 6 and 10. These values are substituted for the parameters x and y in the return expression of sum_of_squares, reducing the expression to

 square(6) + square(10)

If we use the declaration of square once, this reduces to

 (6 * 6) + square(10)

which reduces by multiplication to

 36 + square(10)

A second application of square yields

 36 + (10 * 10)

which reduces by multiplication to

 36 + 100

and finally by addition to

 136

The process we have just described is called the substitution model for function application. It can be taken as a model that determines the “meaning” of function application, insofar as the functions in this chapter are concerned. However, there are two points that should be stressed:

• The purpose of the substitution is to help us think about function application, not to provide a description of how the interpreter really works. Typical interpreters do not evaluate function applications by manipulating the text of a function to substitute values for the parameters. In practice, the “substitution” is accomplished by using a local environment for the parameters. We will discuss this more fully in chapters 3 and 4 when we examine the implementation of an interpreter in detail.

• Over the course of this book, we will present a sequence of increasingly elaborate models of how interpreters work, culminating with a complete implementation of an interpreter and compiler in chapter 5. The substitution model is only the first of these models—a way to get started thinking formally about the evaluation process. In general, when modeling phenomena in science and engineering, we begin with simplified, incomplete models. As we examine things in greater detail, these simple models become inadequate and must be replaced by more refined models. The substitution model is no exception. In particular, when we address in chapter 3 the use of functions with “mutable data,” we will see that the substitution model breaks down and must be replaced by a more complicated model of function application.1

 f(5)

 sum_of_squares(5 + 1, 5 * 2)
 square(5 + 1)  +  square(5 * 2)
 (5 + 1) * (5 + 1) + square(5 * 2)
 (5 + 1) * (5 + 1) + (5 * 2) * (5 * 2)

 6 * (5 + 1) + (5 * 2) * (5 * 2)
 6 * 6 + (5 * 2) * (5 * 2)
 36 + (5 * 2) * (5 * 2)
 36 + 10 * (5 * 2)
 36 + 10 * 10
 36 + 100
 136

 x * x

1.1.6 Conditional Expressions and Predicates

The expressive power of the class of functions that we can declare at this point is very limited, because we have no way to make tests and to perform different operations depending on the result of a test. For instance, we cannot declare a function that computes the absolute value of a number by testing whether the number is negative or not, and taking different actions in each case according to the rule $$|x|=\{\begin{array}{cc}\hfill x& \mathrm{\text{if}}\hfill \end{array}$$ x≥0−xotherwise|x| = \left\{ \begin{array}{rl} x & \mbox{if $x \geq 0$} \\ -x & \mbox{otherwise} \end{array} \right. This construct is a case analysis and can be expressed in JavaScript using a conditional expression as follows:

 function abs(x) {
     return x >= 0 ? x : -x;
 }

The general form of a conditional expression is

 predicate ? consequent-expression : alternative-expression

Conditional expressions begin with a $\textit{predicate}$—that is, an expression whose value is interpreted as either true or false, two distinguished boolean values in JavaScript.1 Note that the primitive boolean expressions true and false trivially evaluate to the boolean values true and false, respectively. The $\textit{predicate}$ is followed by a question mark, the $\textit{consequent-expression}$, a colon, and finally the $\textit{alternative-expression}$.

To evaluate a conditional expression, the interpreter starts by evaluating the $\textit{predicate}$ part of the expression. If the $\textit{predicate}$ evaluates to true, the interpreter evaluates $\textit{consequent-expression}$. Otherwise it evaluates $\textit{alternative-expression}$.

The word predicate is used for functions that return true or false, as well as for expressions that evaluate to true or false. The absolute-value function abs makes use of the primitive predicate >=. This predicate takes two numbers as arguments and tests whether the first number is greater than or equal to the second number, returning true or false accordingly.

JavaScript provides a number of primitive predicates that work similar to >=, including >, <, <=, and ===. In addition to these primitive predicates, there are logical composition operations, which enable us to construct compound predicates. The three most frequently used are these:

• $\textit{expression}_1$ && $\textit{expression}_2$ The interpreter evaluates $\textit{expression}_1$. If it evaluates to false, the value of the whole expression is false, and $\textit{expression}_2$ is not evaluated. If $\textit{expression}_1$ evaluates to true, the value of the whole expression is the value of $\textit{expression}_2$.

• $\textit{expression}_1$ || $\textit{expression}_2$ The interpreter evaluates $\textit{expression}_1$. If it evaluates to true, the value of the whole expresssion is true, and $\textit{expression}_2$ is not evaluated. If $\textit{expression}_1$ evaluates to false, the value of the whole expression is the value of $\textit{expression}_2$.

• ! $\textit{expression}$ The value of the expression is true when $\textit{expression}$ evaluates to false, and false otherwise.

Notice that && and || are not evaluated like arithmetic operators such as +, because their right-hand expression is not always evaluated. The operator !, on the other hand, follows the evaluation rule of section 1.1.3. It is a unary operator, which means that it takes only one argument, whereas the arithmetic operators encountered so far are binary, taking two arguments. The operator ! precedes its argument; we call it a prefix operator. Another prefix operator is the unary “minus” operator, an example of which is the expression -x of the function abs in the beginning of this section.

As an example of how these predicates are used, the condition that a number $x$ be in the range $5 < x < 10$ may be expressed as

 x > 5 && x < 10

Note that the binary operator && has lower precedence than the comparison operators > and <.

 function not_equal(x, y) {
     return x > y || x < y;
 }

or alternatively as

 function not_equal(x, y) {
     return !(x >= y && x <= y);
 }

Note that the operator !== when applied to two numbers, behaves the same as not_equal.

 10;

 5 + 3 + 4;

 9 - 1;

 6 / 2;

 2 * 4 + (4 - 6);

 const a = 3;

 const b = a + 1;

 a + b + a * b;

 a === b;

 b > a && b < a * b 
    ? b : a;

 a === 4 ? 6 : b === 4 ? 6 + 7 + a : 25;

 2 + (b > a ? b : a);

 (a > b
  ? a
  : a < b
    ? b
    : -1)
 *

 (a + 1);

 a === 4 ? 6 : b === 4 ? 6 + 7 + a : 25;

 a === 4
 ? 6
 : b === 4 
   ? 6 + 7 + a
   : 25;

 (5 + 4 + (2 - (3 - (6 + 4 / 5)))) 
 /
 (3 * (6 - 2) * (2 - 7));

 function f(x, y, z) {
    return square(x) + square(y) + square(z) -
           // subtract the square of the smallest
           square(x > y ? (y > z ? z : y) : (x > z ? z : x));
 }

 function plus(a, b) { return a + b; }
 function minus(a, b) { return a - b; }
 function a_plus_abs_b(a, b) {
     return (b >= 0 ? plus : minus)(a, b);
 }

 function p() {
     return p();
 }
 
 function test(x, y) {
     return x === 0 ? 0 : y;
 }

 test(0, p());

1.1.7 Example: Square Roots by Newton’s Method

Functions, as introduced above, are much like ordinary mathematical functions. They specify a value that is determined by one or more parameters. But there is an important difference between mathematical functions and computer functions. Computer functions must be effective.

As a case in point, consider the problem of computing square roots. We can define the square-root function as $$\sqrt{x}=$$  the  y  such that  y≥0  and  y2=x\sqrt{x} =\text{ the }y\text{ such that }y \geq 0\text{ and } y^2 = x This describes a perfectly legitimate mathematical function. We could use it to recognize whether one number is the square root of another, or to derive facts about square roots in general. On the other hand, the definition does not describe a computer function. Indeed, it tells us almost nothing about how to actually find the square root of a given number. It will not help matters to rephrase this definition in pseudo-JavaScript:

 function sqrt(x) {
     return the y with y >= 0 &&
                       square(y) === x;
 }

This only begs the question.

The contrast between mathematical function and computer function is a reflection of the general distinction between describing properties of things and describing how to do things, or, as it is sometimes referred to, the distinction between declarative knowledge and imperative knowledge. In mathematics we are usually concerned with declarative (what is) descriptions, whereas in computer science we are usually concerned with imperative (how to) descriptions.1

How does one compute square roots? The most common way is to use Newton’s method of successive approximations, which says that whenever we have a guess $y$ for the value of the square root of a number $x$, we can perform a simple manipulation to get a better guess (one closer to the actual square root) by averaging $y$ with $x/y$.2 For example, we can compute the square root of 2 as follows. Suppose our initial guess is 1:

Continuing this process, we obtain better and better approximations to the square root.

Now let’s formalize the process in terms of functions. We start with a value for the radicand (the number whose square root we are trying to compute) and a value for the guess. If the guess is good enough for our purposes, we are done; if not, we must repeat the process with an improved guess. We write this basic strategy as a function:

 function sqrt_iter(guess, x) {
     return good_enough(guess, x)
            ? guess
            : sqrt_iter(improve(guess, x), x);
 }

A guess is improved by averaging it with the quotient of the radicand and the old guess:

 function improve(guess, x) {
     return average(guess, x / guess);
 }

where

 function average(x,y) {
     return (x + y) / 2;
 }

We also have to say what we mean by “good enough.” The following will do for illustration, but it is not really a very good test. (See exercise 1.1.7.2.)

 function good_enough(guess, x) {
     return abs(square(guess) - x) < 0.001;
 }

 function sqrt(x) {
     return sqrt_iter(1, x);
 }

If we type these declarations to the interpreter, we can use sqrt just as we can use any function:

 sqrt(9);

 sqrt(100 + 37);

 sqrt(sqrt(2) + sqrt(3));

 square(sqrt(1000));

The sqrt program also illustrates that the simple functional language we have introduced so far is sufficient for writing any purely numerical program that one could write in, say, C or Pascal. This might seem surprising, since we have not any iterative (looping) constructs that direct the computer to do something over and over again. The function sqrt_iter, on the other hand, demonstrates how iteration can be accomplished using no special construct other than the ordinary ability to call a .

 function conditional(predicate, then_clause, else_clause) {		    
     return predicate ? then_clause : else_clause;
 }

 conditional(2 === 3, 0, 5);

 conditional(1 === 1, 0, 5);

 function sqrt_iter(guess, x) {
     return conditional(good_enough(guess, x),
                        guess,
                        sqrt_iter(improve(guess, x),
                                  x));
 }

 const error_threshold = 0.01;
 function good_enough(guess,x) {
     return relative_error(guess, improve(guess, x))
            < error_threshold;
 }
 function relative_error(estimate, reference) {

     return abs(estimate - reference) / reference;
 }

 function good_enough(guess, x) {
     return abs(cube(guess) - x) < 0.001;
 }
 function div3(x, y) {
      return (x + y) / 3;
 }

 function improve(guess, x) {
     return div3(x / (guess * guess), 2 * guess);
 }
 function cube_root(guess, x) {
     return good_enough(guess, x)
                ? guess
                : cuberoot(improve(guess, x), x);
 }

1.1.8 Functions as Black-Box Abstractions

The function sqrt is our first example of a process defined by a set of mutually defined functions. Notice that the declaration of sqrt_iter is recursive; that is, the function is defined in terms of itself. The idea of being able to define a function in terms of itself may be disturbing; it may seem unclear how such a “circular” definition could make sense at all, much less specify a well-defined process to be carried out by a computer. This will be addressed more carefully in section 1.2. But first let’s consider some other important points illustrated by the sqrt example.

Observe that the problem of computing square roots breaks up naturally into a number of subproblems: how to tell whether a guess is good enough, how to improve a guess, and so on. Each of these tasks is accomplished by a separate function. The entire sqrt program can be viewed as a cluster of functions (shown in Figure 1.2) that mirrors the decomposition of the problem into subproblems.

 

The importance of this decomposition strategy is not simply that one is dividing the program into parts. After all, we could take any large program and divide it into parts—the first ten lines, the next ten lines, the next ten lines, and so on. Rather, it is crucial that each function accomplishes an identifiable task that can be used as a module in defining other functions. For example, when we define the good_enough function in terms of square, we are able to regard the square function as a “black box.” We are not at that moment concerned with how the function computes its result, only with the fact that it computes the square. The details of how the square is computed can be suppressed, to be considered at a later time. Indeed, as far as the good_enough function is concerned, square is not quite a function but rather an abstraction of a function, a so-called functional abstraction. At this level of abstraction, any function that computes the square is equally good.

Thus, considering only the values they return, the following two functions squaring a number should be indistinguishable. Each takes a numerical argument and produces the square of that number as the value.1

 function square(x) {
     return x * x;
 }

 function square(x) {
     return math_exp(double(math_log(x)));
 }
 function double(x) {
     return x + x;
 }

So a function should be able to suppress detail. The users of the function may not have written the function themselves, but may have obtained it from another programmer as a black box. A user should not need to know how the function is implemented in order to use it.

 function square(x) {
     return x * x;
 }

 function square(y) {
     return y * y;
 }

 function good_enough(guess, x) {
     return abs(square(guess) - x) < 0.001;
 }

 function sqrt(x) {
     return sqrt_iter(1.0, x);
 }
 function sqrt_iter(guess, x) {
     return good_enough(guess, x)
            ? guess

            : sqrt_iter(improve(guess, x), x);
 }
 function good_enough(guess, x) {
     return abs(square(guess) - x) < 0.001;
 }
 function improve(guess, x) {
     return average(guess, x / guess);
 }

 function sqrt(x) {
     function good_enough(guess, x) {
         return abs(square(guess) - x) < 0.001;
     }
     function improve(guess, x) {
         return average(guess, x / guess);

     }
     function sqrt_iter(guess, x) {
         return good_enough(guess, x) 
                    ? guess
                    : sqrt_iter(improve(guess, x), x);
     }
    return sqrt_iter(1.0, x);
 }

 function sqrt(x) {
     function good_enough(guess) {
         return abs(square(guess) - x) < 0.001;
     }
     function improve(guess) {
         return average(guess, x / guess);

     }
     function sqrt_iter(guess) {
         return good_enough(guess)
                ? guess
                : sqrt_iter(improve(guess));
    }
    return sqrt_iter(1.0);
 }

1.2 Functions and the Processes They Generate

We have now considered the elements of programming: We have used primitive arithmetic operations, we have combined these operations, and we have abstracted these composite operations by declaring them as compound functions. But that is not enough to enable us to say that we know how to program. Our situation is analogous to that of someone who has learned the rules for how the pieces move in chess but knows nothing of typical openings, tactics, or strategy. Like the novice chess player, we don’t yet know the common patterns of usage in the domain. We lack the knowledge of which moves are worth making (which functions are worth declaring). We lack the experience to predict the consequences of making a move (executing a function).

The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity. In becoming an expert photographer, for example, one must learn how to look at a scene and know how dark each region will appear on a print for each possible choice of exposure and development1 conditions. Only then can one reason backward, planning framing, lighting, exposure, and development to obtain the desired effects. So it is with programming, where we are planning the course of action to be taken by a process and where we control the process by means of a program. To become experts, we must learn to visualize the processes generated by various types of functions. Only after we have developed such a skill can we learn to reliably construct programs that exhibit the desired behavior.

A function is a pattern for the local evolution of a computational process. It specifies how each stage of the process is built upon the previous stage. We would like to be able to make statements about the overall, or global, behavior of a process whose local evolution has been specified by a function. This is very difficult to do in general, but we can at least try to describe some typical patterns of process evolution.

In this section we will examine some common “shapes” for processes generated by simple functions. We will also investigate the rates at which these processes consume the important computational resources of time and space. The functions we will consider are very simple. Their role is like that played by test patterns in photography: as oversimplified prototypical patterns, rather than practical examples in their own right.

1.2.1 Linear Recursion and Iteration

We begin by considering the factorial function, defined by $$n!=n\cdot(n-1)\cdot(n-2)\cdots3\cdot2\cdot1$$ There are many ways to compute factorials. One way is to make use of the observation that $n!$ is equal to $n$ times $(n-1)!$ for any positive integer $n$: $$n!=n\cdot\left[(n-1)\cdot(n-2)\cdots3\cdot2\cdot1\right]=n\cdot(n-1)!$$ Thus, we can compute $n!$ by computing $(n-1)!$ and multiplying the result by $n$. If we add the stipulation that 1! is equal to 1, this observation translates directly into a function:

 function factorial(n) {
     return n === 1 
            ? 1
            : n * factorial(n - 1);
 }

 

We can use the substitution model of section 1.1.5 to watch the function in action computing 6!, as shown in figure 1.3.

Now let’s take a different perspective on computing factorials. We could describe a rule for computing $n!$ by specifying that we first multiply 1 by 2, then multiply the result by 3, then by 4, and so on until we reach $n$. More formally, we maintain a running product, together with a counter that counts from 1 up to $n$. We can describe the computation by saying that the counter and the product simultaneously change from one step to the next according to the rule

product $\leftarrow$ counter $\cdot$ product

counter $\leftarrow$ counter $+$ 1 and stipulating that $n!$ is the value of the product when the counter exceeds $n$.

Once again, we can recast our description as a function for computing factorials:1

 function factorial(n) {
     return fact_iter(1, 1, n);
 }
 function fact_iter(product, counter, max_count) {
     return counter > max_count
            ? product

            : fact_iter(counter * product,
                        counter + 1,
                        max_count);
 }

 

As before, we can use the substitution model to visualize the process of computing $6!$, as shown in figure 1.4.

Compare the two processes. From one point of view, they seem hardly different at all. Both compute the same mathematical function on the same domain, and each requires a number of steps proportional to $n$ to compute $n!$. Indeed, both processes even carry out the same sequence of multiplications, obtaining the same sequence of partial products. On the other hand, when we consider the “shapes” of the two processes, we find that they evolve quite differently.

Consider the first process. The substitution model reveals a shape of expansion followed by contraction, indicated by the arrow in figure 1.3. The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). The contraction occurs as the operations are actually performed. This type of process, characterized by a chain of deferred operations, is called a recursive process. Carrying out this process requires that the interpreter keep track of the operations to be performed later on. In the computation of $n!$, the length of the chain of deferred multiplications, and hence the amount of information needed to keep track of it, grows linearly with $n$ (is proportional to $n$), just like the number of steps. Such a process is called a linear recursive process.

By contrast, the second process does not grow and shrink. At each step, all we need to keep track of, for any $n$, are the current values of the names product, counter, and max_count. We call this an iterative process. In general, an iterative process is one whose state can be summarized by the values of a fixed number of state names, together with a fixed rule that describes how the values of the state names should be updated as the process moves from state to state and an (optional) end test that specifies conditions under which the process should terminate. In computing $n!$, the number of steps required grows linearly with $n$. Such a process is called a linear iterative process.

The contrast between the two processes can be seen in another way. In the iterative case, the values of the state names provide a complete description of the state of the process at any point. If we stopped the computation between steps, all we would need to do to resume the computation is to supply the interpreter with the values of the three state names. Not so with the recursive process. In this case there is some additional “hidden” information, maintained by the interpreter and not contained in the state names, which indicates “where the process is” in negotiating the chain of deferred operations. The longer the chain, the more information must be maintained.2

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive function. When we describe a function as recursive, we are referring to the syntactic fact that the function declaration refers (either directly or indirectly) to the function itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a function is written. It may seem disturbing that we refer to a recursive function such as fact_iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state names, and an interpreter need keep track of only three names in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive function consumes an amount of memory that grows with the number of function calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of JavaScript we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive function. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary function call mechanism, so that special iteration constructs are useful only as syntactic sugar.3

 function plus(a, b) {
     return a === 0 ? b : inc(plus(dec(a), b)); 
 }

 function plus(a, b) {
     return a === 0 ? b : plus(dec(a), inc(b));
 }

 plus(4, 5)
 4 === 0 ? 5 : inc(plus(dec(4), 5))
 inc(plus(dec(4), 5))
 ...
 inc(plus(3, 5))
 ...
 inc(inc(plus(2, 5)))
 ...
 inc(inc(inc(plus(1, 5))))
 ...
 inc(inc(inc(inc(plus(0, 5)))))
 inc(inc(inc(inc( 0 === 0 ? 5 : inc(plus(dec(0), 5))))))
 inc(inc(inc(inc( 5 ))))
 inc(inc(inc( 6 )))
 inc(inc( 7 ))
 inc( 8 )
 9

 plus(4, 5)
 4 === 0 ? 5 : plus(dec(4), inc(5))
 plus(dec(4), inc(5))
 ...
 plus(3, 6)
 ...
 plus(2, 7)
 ...
 plus(1, 8)
 ...
 plus(0, 9)
 0 === 0 ? 9 : plus(dec(0), inc(9))
 9

 function A(x,y) {
     return y === 0
            ? 0
            : x === 0
              ? 2 * y
              : y === 1

                ? 2
                : A(x - 1, A(x, y - 1));
 }

 A(1, 10);

 A(2, 4);

 A(3, 3);

 function f(n) {
     return A(0, n);
 }
 function g(n) {
     return A(1, n);
 }

 function h(n) {
     return A(2, n);
 }
 function k(n) {
    return 5 * n * n;
 }

1.2.2 Tree Recursion

Another common pattern of computation is called tree recursion. As an example, consider computing the sequence of Fibonacci numbers, in which each number is the sum of the preceding two: $$0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots$$ In general, the Fibonacci numbers can be defined by the rule $$\begin{array}{ccc}\hfill \mathrm{\text{Fib}}(n)& =\hfill & \hfill \{\begin{array}{cc}0\hfill & \mathrm{\text{if}}\hfill \end{array}\end{array}$$ 1if  Fib(n−1)+Fib(n−2)otherwise\begin{aligned} \textrm{Fib}(n) & = & \left\{ \begin{array}{ll} 0 & \mbox{if }\\ 1 & \mbox{if }\\ \textrm{Fib}(n-1)+\textrm{Fib}(n-2) & \mbox{otherwise} \end{array} \right.\end{aligned}

We can immediately translate this definition into a recursive function for computing Fibonacci numbers:

 function fib(n) {
     return n === 0
            ? 0
            : n === 1
              ? 1
              : fib(n - 1) + fib(n - 2);

 }

 

Consider the pattern of this computation. To compute fib(5) , we compute fib(4) and fib(3) . To compute fib(4) , we compute fib(3) and fib(2) . In general, the evolved process looks like a tree, as shown in figure 1.5. Notice that the branches split into two at each level (except at the bottom); this reflects the fact that the fib function calls itself twice each time it is invoked.

This function is instructive as a prototypical tree recursion, but it is a terrible way to compute Fibonacci numbers because it does so much redundant computation. Notice in figure 1.5 that the entire computation of fib(3)—almost half the work—is duplicated. In fact, it is not hard to show that the number of times the function will compute fib(1) or fib(0) (the number of leaves in the above tree, in general) is precisely $\textrm{Fib}(n+1)$. To get an idea of how bad this is, one can show that the value of $\textrm{Fib}(n)$ grows exponentially with $n$. More precisely (see exercise [ex:fib-proof]), $\textrm{Fib}(n)$ is the closest integer to $\phi^{n} /\sqrt{5}$, where $$\phi=(1+\sqrt{5})/2\approx 1.6180$$ is the golden ratio, which satisfies the equation $$\phi^{2} =\phi + 1$$ Thus, the process uses a number of steps that grows exponentially with the input. On the other hand, the space required grows only linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation. In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

We can also formulate an iterative process for computing the Fibonacci numbers. The idea is to use a pair of integers $a$ and $b$, initialized to $\textrm{Fib}(1)=1$ and $\textrm{Fib}(0)=0$, and to repeatedly apply the simultaneous transformations $$\begin{aligned} a & \leftarrow & a+b \\ b & \leftarrow & a \end{aligned}$$ It is not hard to show that, after applying this transformation $n$ times, $a$ and $b$ will be equal, respectively, to $\textrm{Fib}(n+1)$ and $\textrm{Fib}(n)$. Thus, we can compute Fibonacci numbers iteratively using the function

 function fib(n) {
     return fib_iter(1, 0, n);
 }
 function fib_iter(a, b, count) {
     return count === 0
            ? b

            : fib_iter(a + b, a, count - 1);
 }

This second method for computing $\textrm{Fib}(n)$ is a linear iteration. The difference in number of steps required by the two methods—one linear in $n$, one growing as fast as $\textrm{Fib}(n)$ itself—is enormous, even for small inputs.

One should not conclude from this that tree-recursive processes are useless. When we consider processes that operate on hierarchically structured data rather than numbers, we will find that tree recursion is a natural and powerful tool.1 But even in numerical operations, tree-recursive processes can be useful in helping us to understand and design programs. For instance, although the first fib function is much less efficient than the second one, it is more straightforward, being little more than a translation into JavaScript of the definition of the Fibonacci sequence. To formulate the iterative algorithm required noticing that the computation could be recast as an iteration with three state names.

 function count_change(amount) {
     return cc(amount, 5);
 }
 function cc(amount, kinds_of_coins) {
     return amount === 0
            ? 1

            : amount < 0 ||
              kinds_of_coins === 0
              ? 0
              : cc(amount, kinds_of_coins - 1)
                +
                cc(amount - first_denomination(
                                kinds_of_coins),
                   kinds_of_coins);
 }
 function first_denomination(kinds_of_coins) {
     return kinds_of_coins === 1 ? 1 :
            kinds_of_coins === 2 ? 5 :
            kinds_of_coins === 3 ? 10 :
            kinds_of_coins === 4 ? 25 :
            kinds_of_coins === 5 ? 50 : 0;
 }

 count_change(100);

 // iterative function
 function f_iterative(n) {
     return n < 3
            ? n
            : f_iterative_impl(2, 1, 0, n - 2);
 }

 function f_iterative_impl(a, b, c, count) {
     return count === 0
            ? a
            : f_iterative_impl(a + 2 * b + 3 * c, a, b, count - 1);
 }

 //recursive function
 function f_recursive(n) {
     return n < 3
            ? n
            : f_recursive(n - 1) +
 	     2 * f_recursive(n - 2) +

 	     3 * f_recursive(n - 3);
 }

 function pascal_triangle(row, index) {
     return index > row
            ? false
            : index === 1 || index===row
              ? 1
              : pascal_triangle(row - 1, index - 1)

 	       +
 	       pascal_triangle(row - 1, index);
 }

1.2.3 Orders of Growth

The previous examples illustrate that processes can differ considerably in the rates at which they consume computational resources. One convenient way to describe this difference is to use the notion of order of growth to obtain a gross measure of the resources required by a process as the inputs become larger.

Let $n$ be a parameter that measures the size of the problem, and let $R$($n$) be the amount of resources the process requires for a problem of size $n$. In our previous examples we took $n$ to be the number for which a given function is to be computed, but there are other possibilities. For instance, if our goal is to compute an approximation to the square root of a number, we might take $n$ to be the number of digits accuracy required. For matrix multiplication we might take $n$ to be the number of rows in the matrices. In general there are a number of properties of the problem with respect to which it will be desirable to analyze a given process. Similarly, $R$($n$) might measure the number of internal storage registers used, the number of elementary machine operations performed, and so on. In computers that do only a fixed number of operations at a time, the time required will be proportional to the number of elementary machine operations performed.

We say that $R(n)$ has order of growth $\Theta(f(n))$, written $R(n)=\Theta(f(n))$ (pronounced “theta of $f(n)$”), if there are positive constants $k_1$ and $k_2$ independent of $n$ such that $k_1f(n) \leq R(n) \leq k_2f(n)$ for any sufficiently large value of $n$. (In other words, for large $n$, the value $R(n)$ is sandwiched between $k_1f(n)$ and $k_2f(n)$.)

For instance, with the linear recursive process for computing factorial described in section 1.2.1 the number of steps grows proportionally to the input $n$. Thus, the steps required for this process grows as $\Theta(n)$. We also saw that the space required grows as $\Theta(n)$. For the iterative factorial, the number of steps is still $\Theta(n)$ but the space is $\Theta(1)$—that is, constant.1 The tree-recursive Fibonacci computation requires $\Theta(\phi^{n})$ steps and space $\Theta(n)$, where $\phi$ is the golden ratio described in section 1.2.2.

Orders of growth provide only a crude description of the behavior of a process. For example, a process requiring $n^2$ steps and a process requiring $1000n^2$ steps and a process requiring $3n^2+10n+17$ steps all have $\Theta(n^2)$ order of growth. On the other hand, order of growth provides a useful indication of how we may expect the behavior of the process to change as we change the size of the problem. For a $\Theta(n)$ (linear) process, doubling the size will roughly double the amount of resources used. For an exponential process, each increment in problem size will multiply the resource utilization by a constant factor. In the remainder of section 1.2 we will examine two algorithms whose order of growth is logarithmic, so that doubling the problem size increases the resource requirement by a constant amount.

 function cube(x) {
     return x * x * x;
 }
 function p(x) {
     return 3 * x - 4 * cube(x);
 }

 function sine(angle) {
     return !(abs(angle) > 0.1)
            ? angle
            : p(sine(angle / 3.0));
 }

1.2.4 Exponentiation

Consider the problem of computing the exponential of a given number. We would like a function that takes as arguments a base $b$ and a positive integer exponent $n$ and computes $b^n$. One way to do this is via the recursive definition $$\begin{aligned} b^{n} &=& b\cdot b^{n-1}\\ b^{0} &=&1 \end{aligned}$$ which translates readily into the function

 function expt(b,n) {
     return n === 0
            ? 1
            : b * expt(b, n - 1);
 }

This is a linear recursive process, which requires $\Theta(n)$ steps and $\Theta(n)$ space. Just as with factorial, we can readily formulate an equivalent linear iteration:

 function expt(b,n) {
     return expt_iter(b,n,1);
 }
 function expt_iter(b,counter,product) {
     return counter === 0
            ? product

            : expt_iter(b,
                        counter - 1, 
                        b * product);
 }

This version requires $\Theta(n)$ steps and $\Theta(1)$ space.

We can compute exponentials in fewer steps by using successive squaring. For instance, rather than computing $b^8$ as $$b\cdot(b\cdot(b\cdot(b\cdot(b\cdot(b\cdot(b\cdot b))))))$$ we can compute it using three multiplications: $$\begin{aligned} b^{2} &=& b\cdot b\\ b^{4} &=& b^{2}\cdot b^{2}\\ b^{8} &=& b^{4}\cdot b^{4} \end{aligned}$$

This method works fine for exponents that are powers of 2. We can also take advantage of successive squaring in computing exponentials in general if we use the rule $$\begin{array}{ll} b^{n} =(b^{n/2})^{2} & \mbox{~if is even}\\ b^{n} =b\cdot b^{n-1} & \mbox{~if is odd}\\ \end{array}$$ We can express this method as a function:

 function fast_expt(b, n) {
     return n === 0
            ? 1
            : is_even(n)
              ? square(fast_expt(b, n / 2))
              : b * fast_expt(b, n - 1);

 }

where the predicate to test whether an integer is even is defined in terms of the operator %, which computes the remainder after integer division, by

 function is_even(n) {
     return n % 2 === 0;
 }

The process evolved by fast_expt grows logarithmically with $n$ in both space and number of steps. To see this, observe that computing $b^{2n}$ using fast_expt requires only one more multiplication than computing $b^n$. The size of the exponent we can compute therefore doubles (approximately) with every new multiplication we are allowed. Thus, the number of multiplications required for an exponent of $n$ grows about as fast as the logarithm of $n$ to the base 2. The process has $\Theta(\log n)$ growth.1

The difference between $\Theta(\log n)$ growth and $\Theta(n)$ growth becomes striking as $n$ becomes large. For example, fast_expt for $n=1000$ requires only 14 multiplications.2 It is also possible to use the idea of successive squaring to devise an iterative algorithm that computes exponentials with a logarithmic number of steps (see exercise [ex:iter-expon-pro]), although, as is often the case with iterative algorithms, this is not written down so straightforwardly as the recursive algorithm.3

 function fast_expt_iter(a, b, n){
     return n === 0
            ? a
            : is_even(n)
              ? fast_expt_iter(a, b * b, n / 2)
              : fast_expt_iter(a * b, b, n - 1);

 }
 function fast_expt(b, n){
     return fast_expt_iter(1, b, n);
 }

 function times(a,b) {
     return b === 0
            ? 0
            : a + times(a, b - 1);
 }

 function double(x) {
     return x + x;
 }
 
 function halve(x) {
     return x / 2;
 }

 function fast_times(a, b) { 
     return b === 1
            ? a
            : a === 0 || b === 0
              ? 0
              : is_even(b)
                ? double(fast_times(a, halve(b)))
                : a + fast_times(a, b - 1);
 }

 function double(x) {
     return x + x;
 }
 
 function half(x) {
     return x / 2;
 }

 function fast_times_iter(total, a, b) {
     return b === 1
            ? total + a
            : a === 0 || b===0
              ? 0
              : is_even(b)
                ? fast_times_iter(total, double(a), half(b))
                : fast_times_iter(total + a, a, b - 1);
 }
 
 function times(a, b) {
   return fast_times_iter(0, a, b);
 }

 function fib(n) {
     return fib_iter(1,0,0,1,n);
 }
 function fib_iter(a,b,p,q,count) {
     return count === 0
            ? b
            : is_even(count)
              ? fib_iter(a,
                         b,
                         ??,           // compute p'
                         ??,           // compute q'
                         count / 2)
              : fib_iter(b * q + a * q + a * p,
                         b * p + a * q,
                         p,
                         q,
                         count - 1);
 }

 function fib(n) {
     return fib_iter(1, 0, 0, 1, n);
 }
 
 function fib_iter(a, b, p, q, count) {
     return count === 0
            ? b

            : is_even(count)
              ? fib_iter(a,
    	                b,
 	                p * p + q * q,
 	                2 * p * q + q * q,
 	                count / 2)
              : fib_iter(b * q + a * q + a * p,
                         b * p + a * q,
                         p,
                         q,
                         count - 1);
 }